package com.yanceysong.codetop.s1_s10;

import java.util.Arrays;

/**
 * @ClassName S7_Mid_53_最大子数组和
 * @Description LeetCode 53 - 最大子数组和
 * @date 2025/8/29
 * @Author Cascade
 * @Version 2.0
 */
public class S7_Mid_53_最大子数组和 {
    /**
     * LeetCode链接:
     * <a href="https://leetcode.cn/problems/maximum-subarray/description/">...</a>
     * <p>
     * 题目描述:
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * 子数组是数组中的一个连续部分。
     * <p>
     * 示例:
     * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 输出：6
     * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6。
     * <p>
     * 解题思路:
     * 1. 贪心算法: {@link #maxSubArray(int[])}
     * 2. 动态规划: {@link #maxSubArrayWithDp(int[])}
     * ==================== 解法1: 贪心算法 ====================
     * <p>
     * 算法思路:
     * 1. 初始化两个变量：`maxSum` 存储全局最大和，`currentSum` 存储当前子数组的和。
     * 2. 遍历数组，将当前元素累加到 `currentSum`。
     * 3. 每次累加后，更新 `maxSum` 为 `max(maxSum, currentSum)`。
     * 4. 核心贪心思想：如果 `currentSum` 变为负数，说明它对后续的子数组和不再有贡献（反而会拖累），
     * 因此，将 `currentSum` 重置为0，相当于从下一个元素重新开始计算子数组。
     * <p>
     * 执行示例: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
     * <p>
     * 初始状态: maxSum = -2, currentSum = 0
     * <p>
     * 遍历过程:
     * num = -2: currentSum = -2.  maxSum = max(-2, -2) = -2.  currentSum < 0, 重置 currentSum = 0.
     * num =  1: currentSum =  1.  maxSum = max(-2,  1) =  1.
     * num = -3: currentSum = -2.  maxSum = max( 1, -2) =  1.  currentSum < 0, 重置 currentSum = 0.
     * num =  4: currentSum =  4.  maxSum = max( 1,  4) =  4.
     * num = -1: currentSum =  3.  maxSum = max( 4,  3) =  4.
     * num =  2: currentSum =  5.  maxSum = max( 4,  5) =  5.
     * num =  1: currentSum =  6.  maxSum = max( 5,  6) =  6.
     * num = -5: currentSum =  1.  maxSum = max( 6,  1) =  6.
     * num =  4: currentSum =  5.  maxSum = max( 6,  5) =  6.
     * <p>
     * 最终结果: maxSum = 6
     * <p>
     * 时间复杂度: O(n)，只需遍历一次数组。
     * 空间复杂度: O(1)，只使用常数个额外变量。
     * <p>
     * =======================================================
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int maxSum = nums[0];
        int currentSum = 0;
        for (int num : nums) {
            currentSum += num;
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
            if (currentSum < 0) {
                currentSum = 0;
            }
        }
        return maxSum;
    }

    /**
     * ==================== 解法2: 动态规划 ====================
     * <p>
     * 算法思路:
     * 1. 定义 `dp[i]` 为：以 `nums[i]` 结尾的连续子数组的最大和。
     * 2. 状态转移方程：
     * - 如果 `dp[i-1]` > 0，说明前一个子数组的和是正增益，可以接上当前元素：`dp[i] = dp[i-1] + nums[i]`
     * - 如果 `dp[i-1]` <= 0，说明前一个子数组的和是负增益或零，不如从当前元素重新开始：`dp[i] = nums[i]`
     * 3. 最终结果是所有 `dp[i]` 中的最大值，而不是 `dp[n-1]`，因为最大子数组可能在任何位置结束。
     * <p>
     * 执行示例: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
     * <p>
     * DP Table 构建过程:
     * i=0: dp[0] = -2.                                    (res = -2)
     * i=1: dp[0]<0, dp[1] = nums[1] = 1.                  (res = max(-2, 1) = 1)
     * i=2: dp[1]>0, dp[2] = dp[1] + nums[2] = 1 - 3 = -2. (res = max(1, -2) = 1)
     * i=3: dp[2]<0, dp[3] = nums[3] = 4.                  (res = max(1, 4) = 4)
     * i=4: dp[3]>0, dp[4] = dp[3] + nums[4] = 4 - 1 = 3.  (res = max(4, 3) = 4)
     * i=5: dp[4]>0, dp[5] = dp[4] + nums[5] = 3 + 2 = 5.  (res = max(4, 5) = 5)
     * i=6: dp[5]>0, dp[6] = dp[5] + nums[6] = 5 + 1 = 6.  (res = max(5, 6) = 6)
     * i=7: dp[6]>0, dp[7] = dp[6] + nums[7] = 6 - 5 = 1.  (res = max(6, 1) = 6)
     * i=8: dp[7]>0, dp[8] = dp[7] + nums[8] = 1 + 4 = 5.  (res = max(6, 5) = 6)
     * <p>
     * 最终DP数组: dp = [-2, 1, -2, 4, 3, 5, 6, 1, 5]
     * 最终结果: res = 6
     * <p>
     * 空间优化:
     * 由于 `dp[i]` 只依赖于 `dp[i-1]`，可以使用一个变量 `currentMax` 替代 `dp` 数组，
     * 将空间复杂度从 O(n) 优化到 O(1)。优化后的代码逻辑与贪心法非常相似。
     * <p>
     * 时间复杂度: O(n)，遍历一次数组。
     * 空间复杂度: O(n)，使用了一个DP数组。可优化至O(1)。
     * <p>
     * =======================================================
     */
    public int maxSubArrayWithDp(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        int res = dp[0];

        for (int i = 1; i < len; i++) {
            // 状态转移方程
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
            // 更新全局最大值
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        S7_Mid_53_最大子数组和 solution = new S7_Mid_53_最大子数组和();
        System.out.println("=== 最大子数组和测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testCase(solution, new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}, 6, "题目示例");

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testCase(solution, new int[]{1}, 1, "单元素数组");
        testCase(solution, new int[]{-1}, -1, "单负元素数组");
        testCase(solution, new int[]{5, 4, 3, 2, 1}, 15, "全正数数组");
        testCase(solution, new int[]{-1, -2, -3, -4, -5}, -1, "全负数数组");

        // 测试3: 特殊情况测试
        System.out.println("\n--- 测试3: 特殊情况测试 ---");
        testCase(solution, new int[]{0, 0, 0, 0}, 0, "全零数组");
        testCase(solution, new int[]{-2, 1, -3, 4, 0, 2, 1, -5, 4}, 7, "包含零的数组");
        testCase(solution, new int[]{1, -1, 1, -1, 1}, 1, "正负交替数组");

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 统一的测试用例方法
     *
     * @param solution    解决方案实例
     * @param nums        输入数组
     * @param expected    期望结果
     * @param description 测试描述
     */
    private static void testCase(S7_Mid_53_最大子数组和 solution, int[] nums, int expected, String description) {
        System.out.println("测试描述: " + description);
        System.out.println("输入数组: " + Arrays.toString(nums));

        // 测试贪心算法
        int actualGreedy = solution.maxSubArray(nums);
        System.out.println("  - 贪心法 -> 结果: " + actualGreedy + ", 期望: " + expected);
        assert actualGreedy == expected : description + " (贪心法) 测试失败";

        // 测试动态规划
        int actualDp = solution.maxSubArrayWithDp(nums);
        System.out.println("  - DP法   -> 结果: " + actualDp + ", 期望: " + expected);
        assert actualDp == expected : description + " (DP法) 测试失败";

        // 验证两种方法结果一致
        assert actualGreedy == actualDp : description + ": 两种方法结果不一致";

        System.out.println("  ✓ 测试通过");
    }
}
